// https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

// 算法思路总结：
// 1. 迭代实现二叉树前序遍历
// 2. 使用栈模拟递归过程保存节点
// 3. 沿左子树深度遍历并记录节点值
// 4. 转向右子树继续遍历过程
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <stack>
#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while (cur != nullptr || st.empty() == false)
        {
            while (cur != nullptr)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }

        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"1","null","2","3"};
    vector<string> nodes2 = {"1","2","3","4","5","null","8","null","null","6","7","9"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    auto v1 = sol.preorderTraversal(root1);
    auto v2 = sol.preorderTraversal(root2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl; 

    return 0;
}